//
//  BinaryTreeNode.swift
//
//  Created by Renju Jiang on 2018/7/17.
//  Copyright © 2018年 jiangrenju. All rights reserved.
//

import Foundation

class BinaryTreeNode {
    var value: Int
    var left: BinaryTreeNode?
    var right: BinaryTreeNode?
    
    init(value: Int) {
        self.value = value
    }
}

class BinaryTreeNodeAlgorithm {
    func getBinaryTreeNodeDepth(root: BinaryTreeNode?) -> Int {
        guard root != nil else { return 0 }
        
        let left = getBinaryTreeNodeDepth(root: root?.left)
        let right = getBinaryTreeNodeDepth(root: root?.right)
        
        return max(left, right) + 1
    }
    
    func isBalancedTreeNode(root: BinaryTreeNode?) -> Bool {
        if root == nil {
            return true
        }
        
        let left = getBinaryTreeNodeDepth(root: root?.left)
        let right = getBinaryTreeNodeDepth(root: root?.right)
        if abs(left-right) > 1 {
            return false
        }
        return isBalancedTreeNode(root: root?.left) && isBalancedTreeNode(root: root?.right)
    }
    
    func isBalanceTreeNode2(root: BinaryTreeNode?, depth: inout Int) -> Bool {
        if root == nil {
            return true
        }
        
        var left = 0, right = 0
        
        if !isBalanceTreeNode2(root: root?.left, depth: &left) {
            return false
        }
        
        if !isBalanceTreeNode2(root: root?.right, depth: &right) {
            return false
        }
        
        if abs(left-right) > 1 {
            return false
        }
        
        depth = max(left, right) + 1
        
        return true
    }
    
    static var index = 0
    func kthNode(root: BinaryTreeNode?, k: Int) -> BinaryTreeNode? {
        if root == nil {
            return nil
        }
        
        var node = kthNode(root: root?.left, k: k)
        if node != nil {
            return node
        }
        
        BinaryTreeNodeAlgorithm.index += 1
        
        if BinaryTreeNodeAlgorithm.index == k {
            return root
        }
        
        node = kthNode(root: root?.right, k: k)
        
        if node != nil {
            return node
        }

        return nil
    }
    
    func preOrder2(root: BinaryTreeNode?) {
        
        var s = Stack<BinaryTreeNode>()
        var p = root
        
        while p != nil || !s.isEmpty {
            
            while p != nil {
                print("\(p!.value)")
                s.push(p!)
                p = p!.left
            }
            
            if !s.isEmpty {
                p = s.peek()
                _ = s.pop()
                p = p?.right
            }
        }
        
        
    }
    
    
    
    
    
}
